package lc.q1_50;


import java.util.*;

/**
 * 30. 串联所有单词的子串
 * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 *
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：
 *   s = "barfoothefoobarman",
 *   words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：
 * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
 * 输出的顺序不重要, [9,0] 也是有效答案。
 * 示例 2：
 *
 * 输入：
 *   s = "wordgoodgoodgoodbestword",
 *   words = ["word","good","best","word"]
 * 输出：[]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q30 {

    public List<Integer> findSubstring2(String s, String[] words) {
        if (words.length == 0) {
            return new ArrayList<>();
        }
        Arrays.sort(words);
        Map<String, Integer> wordTimes = new HashMap<>();
        for (String word : words) {
            final Integer integer = wordTimes.computeIfAbsent(word, w -> 0);
            wordTimes.put(word, integer +1);
        }
        List<Integer> integers = new ArrayList<>();
        final int wordLength = words[0].length();
        out: for (int i = 0; i < s.length() - wordLength*words.length+1; i++) {
            // 更简单的方式，直接看次数
            final HashMap<String, Integer> mp = new HashMap<>(wordTimes);
            for (int j = 0; j < words.length; j++) {
                // 存在查过多次的，是否可以标记出来，直接过滤掉前面的查询
                String s1 = s.substring(i + j * wordLength, i + j * wordLength + wordLength);
                final int integer = mp.computeIfAbsent(s1, sk -> 0);
                if (integer == 0) {
                    continue out;
                } else {
                    mp.put(s1, integer - 1);
                }

            }
            integers.add(i);
        }
        return integers;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        Arrays.sort(words);
        String wordsJoin = String.join("", words);
        HashMap<Integer, String> treeMap = new HashMap<>();
        Set<String> hasCheck = new HashSet<>();
        for (String word : words) {
            // 寻找s中所有的
            if (hasCheck.contains(word)) {
                continue;
            }
            int j = 0;
            for (int i = 0; i < s.length();i ++) {
                if (treeMap.containsKey(i)) {
                    continue;
                }
                final int index = s.indexOf(word, i);
                if (index == -1) {
                    break;
                }
                j ++;
                treeMap.put(index, word);
                // 如果对于某个单词，没有任何匹配，则显然可以放弃掉了
            }
            hasCheck.add(word);
            if (j == 0) {
                return new ArrayList<>();
            }
        }
        final ArrayList<Integer> integers = new ArrayList<>();
        if (treeMap.isEmpty()) {
            return integers;
        }
        // 创建一个数组

        final int length = words[0].length();
        final int wordCount = words.length;
        for (int i : treeMap.keySet()) {
            List<String> wds = new ArrayList<>();
            for (int j = 0; j < wordCount; j++) {
                final String j1 = treeMap.get(j*length + i);
                if (j1 != null) {
                    wds.add(j1);
                }
            }
            if (wds.size() < wordCount) {
                continue;
            }
            wds.sort(String::compareTo);
            if (String.join("", wds).equals(wordsJoin)) {
                integers.add(i);
            }
        }
        return integers;
    }

    public static void main(String[] args) {
        final Q30 q30 = new Q30();
        final List<Integer> barfoothefoobarman = q30.findSubstring2("aaaaaaaa", new String[]{"aa","aa","aa"});
        System.out.println(barfoothefoobarman);
    }


}
